package graph;

/*
* 课程表
* 使用拓扑排序算法, 判断是否为一个有向无环图
*       先遍历将统计开始时入度为0的节点,并加入队列
*       每次从队列中某个入度为0的节点出发, 并将他的临界点的入度减一.继续将入度为0的节点加入队列, 循环这个步骤
*       循环中统计入度为0的个数, 最后等于numCourses则为true
*
* */

import java.util.LinkedList;
import java.util.List;

public class CanFinish207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
       int[] input=new int[numCourses];
        for (int[] pre : prerequisites) {
            input[pre[0]]++;
        }
        LinkedList<Integer> queue=new LinkedList<>();
        // 找出入度为0的节点, 并入队列.  切记入队的是节点,不是入度数, i表示节点, input[i]表示i节点的入度个数
        for(int i=0;i<numCourses;i++){
            if(input[i]==0) {
                queue.addLast(i);
            }
        }
        int count=0;
        while(!queue.isEmpty()){
            int node=queue.removeFirst();
            count++;
            for (int[] pre : prerequisites) {
                if(pre[1]==node){
                    input[pre[0]]--;
                    if(input[pre[0]]==0){
                        queue.addLast(pre[0]);
                    }
                }
            }
        }
        return count==numCourses;
    }
}
